﻿//79. 单词搜索
//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
//如果 word 存在于网格中，返回 true ；否则，返回 false 。
//单词必须按照字母顺序，通过相邻的单元格内的字母构成，
//其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
public:
    bool bfs(vector<vector<char>>& board, string& word, int i, int j, int cur, vector<vector<int>>& arr)
    {
        int z = word.size() - 1;
        int m = board.size();
        int n = board[0].size();
        if (cur > z) return false;
        if (i >= m || i < 0 || j >= n || j < 0 || arr[i][j])  return false;
        if (board[i][j] != word[cur])    return false;
        if (cur == z)  return true;
        arr[i][j] = 1;
        bool found = bfs(board, word, i + 1, j, cur + 1, arr) ||
            bfs(board, word, i - 1, j, cur + 1, arr) ||
            bfs(board, word, i, j + 1, cur + 1, arr) ||
            bfs(board, word, i, j - 1, cur + 1, arr);
        arr[i][j] = 0;
        return found;
    }


    bool exist(vector<vector<char>>& board, string word)
    {
        if (board.empty())
            return false;
        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> arr(m, (vector<int>(n, 0)));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0] && bfs(board, word, i, j, 0, arr))
                {
                    return true;
                }

            }
        }
        return false;
    }
};